The present invention relates generally to wireless communication. More particularly, the invention relates to location based routing in a wireless ad-hoc network.
Most commercial public wireless networks contain a significant amount of network infrastructure which allows mobile wireless devices (e.g., wireless telephones) to communicate with each other as well as with other networks (e.g., a wired telephone network). In such networks, the infrastructure, which includes components such as base stations and other network controllers, handles network control and routing operations. The locations of the network infrastructure components are fixed, and the locations of the various components are designed to provide a desired level of network performance. Thus, each wireless device communicates directly with fixed network infrastructure components.
In areas where there is little or no communication infrastructure, wireless devices may communicate with each other by organizing into an ad-hoc wireless network. Ad-hoc wireless networks have no central control, and each wireless device which is part of the network operates as an individual communication device as well as part of the network infrastructure. Thus, each wireless device may originate and receive messages, but each wireless device also functions to route messages between other wireless devices which may otherwise be unable to directly communicate with each other. Instead of relying on wireless network infrastructure for communication, ad-hoc wireless networks rely on peer-to-peer interactions for network communication. There are many applications for ad-hoc wireless networks. For example, military personnel on the field of battle; emergency disaster relief personnel coordinating efforts where there is no wireless infrastructure; and informal gatherings where participants wish to communicate with each other. It is also noted that ad-hoc wireless networks are useful for devices other than telephones, for example wireless PDAs, computers, or any other type of communication device.
The varying network topology of a wireless ad-hoc network complicates data packet routing. In a conventional wireless network, which utilizes fixed network infrastructure, the topology of the network is static, and each of the routing nodes in the network maintains network topology information to assist in the routing determination. However, the network topology in a wireless ad-hoc network changes quickly, with new links being created and existing links being torn down, as each of the wireless devices moves around in the network. Maintaining overall network topology in each of the mobile nodes is difficult, requiring significant bandwidth in order to constantly propagate the changing topology among the nodes. In order to maintain up-to-date network topology information, each mobile node periodically broadcasts its position information to other nodes in a process called “flooding”.
One type of routing used in ad-hoc wireless networks is location based routing. In this type of routing, each of the network nodes stores location information about the other network nodes. Thus, when a particular network node needs to send a data packet to a destination node, the last known location of the destination node is used in order to determine network routing. For example, assume that node A needs to transmit a data packet to a node B, but node B is not in direct communication with node A, so that node A needs to transmit the packet to an intermediate node that is in communication with node A. Node A checks a list of neighbor nodes (i.e., those nodes that A may directly communicate with), and based on stored location information, chooses the neighbor node that is closest to the last known location of destination node B, and forwards the packet to the chosen neighbor node. The chosen neighbor node performs the same steps, and this processing continues until the data packet reaches destination node B.
While the above described location based routing provides certain advantages, it also presents problems. For example, the nodes in the ad-hoc wireless network are mobile, and as such, their stored location information for any particular destination node may be obsolete, or at least somewhat stale. As such, a data packet may arrive at a next-to-last hop node only to find out that the destination node has moved and is no longer in communication with the next-to-last hop node. As such, the data packet may be undeliverable to the destination node.
More up-to-date location information may be maintained by each of the network nodes in order to mitigate the above described routing problem. However, as described above, this would require more frequent location information broadcast messages (i.e., flooding) to be transmitted among the nodes, thereby causing additional bandwidth overhead (i.e., bandwidth usage for network control rather than data transmission) and also requiring additional power consumption at the wireless nodes. Thus, a balance between up-to-date network node location information and network overhead/power consumption has been an ongoing problem in ad-hoc wireless networks.
What is needed is an improved routing protocol and location information update technique for ad-hoc wireless networks.